Elea fu fondata nella seconda metà del VI secolo a.C., da esuli Focei in fuga dalla Ionia (sulle coste dell'attuale Turchia, nei pressi del golfo di Smirne) per sfuggire alla pressione militare persiana.

La fondazione avvenne a seguito della Battaglia di Alalia, combattuta dai Focei di Alalia contro una coalizione di Etruschi e Cartaginesi, evento databile in un arco temporale che va dal 541 al 535 a.C.La città fu edificata sulla sommità e sui fianchi di un promontorio, comprato dai Focei agli Enotri, situato tra Punta Licosa e Palinuro. Il nome Hyele, con cui fu inizialmente chiamata, era lo stesso della sorgente posta alle spalle del promontorio.Intorno al V secolo a.C., la città era felicemente nota per i floridi rapporti commerciali e la politica governativa. Assunse anche notevole importanza culturale per la sua famosa tradizione filosofica pre-socratica, detta Scuola eleatica, fondata da Parmenide e portata avanti dal suo allievo Zenone.

Nel IV secolo entrò nella lega delle città impegnate ad arrestare l'avanzata dei Lucani, che avevano già occupato la vicina Poseidonia (Paestum) e minacciavano Elea.Con Roma, invece, Elea intrattenne ottimi rapporti: fornì navi per le guerre puniche (III-II secolo) e inviò giovani sacerdotesse per il culto a Demetra (Cerere), provenienti dalle famiglie aristocratiche del posto. Divenne infine luogo di villeggiatura e di cura per aristocratici romani, forse grazie anche alla presenza della scuola medico-filosofica.Nell'88 a.C. Elea fu ascritta alla tribù Romilia, divenendo municipio romano con il nome di Velia (cfr. la scheda a lato, Le diverse forme del nome greco), ma con il diritto di mantenere la lingua greca e di battere moneta propria. Nella seconda metà del I secolo servì come base navale, prima per Bruto (44 a.C.) e poi per Ottaviano (38 a.C.).

La prosperità della città continuò fino a tutto il I secolo d.C., quando si costruirono numerose ville e piccoli insediamenti, unitamente a nuovi edifici pubblici e alle thermae, ma il progressivo insabbiamento dei porti e la costruzione, avviata nel 132 a.C., della Via Popilia che collegava Roma con il sud della penisola tagliando fuori Velia, condussero la città a un progressivo isolamento e impoverimento.

Dalla fine dell'età imperiale, gli ultimi abitanti furono costretti a rifugiarsi nella parte alta dell'Acropoli per sfuggire all'avanzamento del terreno paludoso, e l'insediamento è riportato nei codici con vari nomi, corrispondenti a differenti periodi, tra cui Castellammare della Bruca.Alla fine del Medioevo, nel 1420, diventò feudo dei Sanseverino che però il 21 marzo del 1466, lo donarono alla Real Casa dell'Annunziata di Napoli. Dal 1669 non è più censito alcun abitante sul posto, e le tracce della città si perdono nelle paludi.

Solo nell'Ottocento l'archeologo François Lenormant comprese che l'importanza storica e culturale del luogo si prestava a interessanti studi e approfondimenti, tuttora in corso, ma va anche rilevato che purtroppo, a causa degli scavi iniziati nel secolo scorso, ciò che restava dell'abitato dall'epoca medievale fino al Seicento fu quasi completamente distrutto.